/***************************************************************************************
* Copyright (c) 2014-2022 Zihao Yu, Nanjing University
*
* NEMU is licensed under Mulan PSL v2.
* You can use this software according to the terms and conditions of the Mulan PSL v2.
* You may obtain a copy of Mulan PSL v2 at:
*          http://license.coscl.org.cn/MulanPSL2
*
* THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
* EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
* MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
*
* See the Mulan PSL v2 for more details.
***************************************************************************************/

#include <isa.h>

/* We use the POSIX regex functions to process regular expressions.
 * Type 'man regex' for more information about POSIX regex functions.
 */
#include <regex.h>

word_t paddr_read(paddr_t addr, int len);

enum {
  TK_NOTYPE = 256, TK_EQ,TK_NUM,TK_NEG,TK_NEQ,TK_AND,TK_POINTER,TK_REG,TK_HEX
  //enum类型，数值以第一个为基准递增
  /* TODO: Add more token types */

};
//用于正则匹配的token
static struct rule {
  const char *regex;
  int token_type;
} rules[] = {

  /* TODO: Add more rules.
   * Pay attention to the precedence level of different rules.
   */

  {" +", TK_NOTYPE},    // spaces
  {"\\+", '+'},         // plus
  {"-",'-'},            //sub
  {"\\*",'*'},          //multiply
  {"/",'/'},            //divide
  {"\\(",'('},          //(
  {"\\)",')'},          //)
  //{"\\d+", TK_DECIMAL}, // 匹配十进制数字
  {"==", TK_EQ},        // equal
  {"!=", TK_NEQ},       //not equal
  {"&&",TK_AND},
  {"\\b[0-9]+\\b",TK_NUM}, //number
  {"\\$($0|ra|[sgt]p|t[0-6]|a[0-7]|s[0-9]|s10|s11)",TK_REG},
  {"0[xX][0-9A-Fa-f]+",TK_HEX},
  {"&&",TK_AND},
};

#define NR_REGEX ARRLEN(rules)

static regex_t re[NR_REGEX] = {};

/* Rules are used for many times.
 * Therefore we compile them only once before any usage.
 */
void init_regex() {//编译正则表达式用的,编译成内部使用的
  int i;
  char error_msg[128];
  int ret;

  for (i = 0; i < NR_REGEX; i ++) {
    ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
    if (ret != 0) {
      regerror(ret, &re[i], error_msg, 128);
      panic("regex compilation failed: %s\n%s", error_msg, rules[i].regex);
    }
  }
}

typedef struct token {
  int type;
  char str[32];
} Token;

static Token tokens[32] __attribute__((used)) = {};
static int nr_token __attribute__((used))  = 0;

static bool make_token(char *e) {
  int position = 0;
  int i;
  regmatch_t pmatch;

  nr_token = 0;

  while (e[position] != '\0') {
    /* Try all rules one by one. */
    for (i = 0; i < NR_REGEX; i ++) {
      if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) {
        char *substr_start = e + position;
        int substr_len = pmatch.rm_eo;

        Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s",
            i, rules[i].regex, position, substr_len, substr_len, substr_start);

        position += substr_len;

        /* TODO: Now a new token is recognized with rules[i]. Add codes
         * to record the token in the array `tokens'. For certain types
         * of tokens, some extra actions should be performed.
         */

        Token new_token;
        switch (rules[i].token_type) {
          case TK_NOTYPE: break;
          default: 
            strncpy(new_token.str,substr_start,substr_len);
            new_token.str[substr_len]='\0';
            new_token.type=rules[i].token_type;
            tokens[nr_token]=new_token;
            nr_token+=1;
            break;
        }

        break;//if 的 berak （？）
      }
    }

    if (i == NR_REGEX) {
      printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
      return false;
    }
  }

  return true;
}


//用于判断阔后匹配的
typedef struct Stack {
    int top;
    unsigned capacity;
    char* array;
} Stack;

Stack* createStack(unsigned capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->top = -1;
    stack->capacity = capacity;
    stack->array = (char*)malloc(stack->capacity * sizeof(char));
    return stack;
}

bool isEmpty(Stack* stack) {
    return stack->top == -1;
}

void push(Stack* stack, char item) {
    stack->array[++stack->top] = item;
}

char pop(Stack* stack) {
    if (isEmpty(stack)) {
        return '\0';
    }
    return stack->array[stack->top--];
}


//用栈判断()是否匹配
/*bool check_parentheses(word_t p, word_t q){
  if(tokens[p].type!='('||tokens[q].type!=')') return false;
  Stack* stack = createStack(q - p + 1);
    for (int i = p; i <= q; i++) {
        if (tokens[i].type == '(') {
            push(stack, tokens[i].type);
        } else if (tokens[i].type == ')') {
            if (isEmpty(stack)) {
                return false;
            }
            pop(stack);
        }
    }
    return isEmpty(stack);
  //return legal;
}
*/

bool check_parentheses(word_t p,word_t q)
{
  bool flag=false;
  if(tokens[p].type=='(' && tokens[q].type == ')')
  {
    for(int i =p+1;i<q;)
    {
      
      if (tokens[i].type==')')
      {
        
        break;
      }
 
      else if (tokens[i].type=='(')
      {
        while(tokens[i+1].type!=')' )
        {
          i++;
          if(i==q-1)
          {
            
            break;
          }
        }
        i+=2;
      }
 
      else i++;
        
    }
    flag=true;
  }
  return flag;
}

word_t major_expr(word_t p,word_t q){
  word_t ret=0;
  word_t par=0;
  word_t op_type=0;
  word_t tmp_type=0;
  for(word_t i=p;i<=q;i++){
    if(tokens[i].type=='-'){
      if(i==p){//only the start of the token has the posibility to be negative number
        tokens[i].type=TK_NEG;
        return i;
      }
    }
    for (int i = 0; i < nr_token; i ++){
      if (tokens[i].type =='*'&&
          (i == 0||(tokens[i-1].type!=')'||tokens[i - 1].type !=TK_NUM))){
        tokens[i].type = TK_POINTER;
        return i;
      }
    }
    
    //数字
    if (tokens[i].type ==TK_NUM){
      continue;
    }
    else if (tokens[i].type=='('){
      par++;
      continue;
    }
    else if (tokens[i].type==')')
    {
      if (par==0){
        return -1;
      }
      par--;
    }
    else if (par>0){
      continue;
    }
    else{
      switch (tokens[i].type) {
        case '*': case '/': tmp_type = 1; break;
        case '+': case '-': tmp_type = 2; break;
        case TK_EQ:case TK_NEQ:tmp_type=3;break;
        case TK_AND:tmp_type=4;break;
        default: assert(0);
      }
      if (tmp_type>=op_type){
        op_type=tmp_type;
        ret=i;
      }  
    }
 
  }
  if(par>0) return -1;
  return ret;
}


word_t eval(word_t p, word_t q) {
  if (p > q) {
    /* Bad expression */
    printf("worng input, because p>q\nthe program will be quitted by assert");
    assert(0);
  }
  else if (p == q) {//单个的token，最小的处理单位，可能是数字，寄存器或者16进制数
    /* Single token.
     * For now this token should be a number.
     * Return the value of the number.
     */
    if (tokens[p].type==TK_NUM){
      word_t num;
      sscanf(tokens[p].str,"%d",&num);
      return num;
    }
    else if(tokens[p].type==TK_REG){
      word_t num;
      bool t = true;
      num = isa_reg_str2val(tokens[p].str, &t);
      if (!t) num=0;
      return num;

    }
    else if(tokens[p].type==TK_HEX){
      return strtol(tokens[p].str,NULL,16);
    }
    else{
      printf("no condition\n");
    }
  }
  else if (check_parentheses(p, q) == true) {
    /* The expression is surrounded by a matched pair of parentheses.
     * If that is the case, just throw away the parentheses.
     */
    return eval(p + 1, q - 1);
  }
  else {
    int op = major_expr(p,q);//当前expr的主运算符

    int val2 = eval(p,op-1);

    if(tokens[op].type==TK_NEG){
      val2=-val2;
      return val2;
    }      
    if(tokens[op].type==TK_POINTER){
      return paddr_read(val2,4);
    }
    int32_t val1 = eval(p, op - 1);//写在后是为了防止op是负数导致eval传入的p>q
    //int32_t val=0;
    switch (tokens[op].type) {
      case '+': return val1 + val2;
      case '-': return val1 - val2;
      case '*': return val1 * val2;
      case '/': return val1 / val2;
      case TK_EQ: return val1==val2;
      case TK_NEQ:return val1!=val2;
      case TK_AND:return val1&&val2;
      default: assert(0);
    }
  }
  return 0;
}

word_t expr(char *e, bool *success) {
  if (!make_token(e)) {
    *success = false;
    return 0;
  }
  for(int h=0;h<nr_token;h++){
    printf("%d %s ;",tokens[h].type,tokens[h].str);
  }
  /* TODO: Insert codes to evaluate the expression. */
  return eval(0,nr_token-1);//求值函数

}
